A comparison of the Extrapolated Successive Overrelaxation and the Preconditioned Simultaneous Displacement methods for augmented linear systems

摘要

In this paper we study the impact of two types of preconditioning on thenumerical solution of large sparse augmented linear systems. The firstpreconditioning matrix is the lower triangular part whereas the second is theproduct of the lower triangular part with the upper triangular part of theaugmented system's coefficient matrix. For the first preconditioning matrix weform the Generalized Modified Extrapolated Successive Overrelaxation (GMESOR)method, whereas the second preconditioning matrix yields the GeneralizedModified Preconditioned Simultaneous Displacement (GMPSD) method, which is anextrapolated form of the Symmetric Successive Overrelaxation method. We findsufficient conditions for each aforementioned iterative method to converge. Inaddition, we develop a geometric approach, for determining the optimum valuesof their parameters and corresponding spectral radii. It is shown that bothiterative methods studied (GMESOR and GMPSD) attain the same rate ofconvergence. Numerical results confirm our theoretical expectations.